package com.lzh.linkedlistself;

/**
 * @Author: liuzh
 * @Date:2021-09-01 下午12:53
 * @Description:实现两个单链表有序合并为一个单链表
 */
public class SortTwoLinkedList {
    public static void main(String[] args) {
        Node node1 = new Node(1, "a");
        Node node2 = new Node(2, "b");
        Node node3 = new Node(3, "c");
        Node node4 = new Node(4, "d");
        Node node5 = new Node(5, "e");
        Node node6 = new Node(6, "f");
        SingleLinkedListOne singleLinkedListOne1 = new SingleLinkedListOne();
        singleLinkedListOne1.addOrder(node3);
        singleLinkedListOne1.addOrder(node1);
        singleLinkedListOne1.addOrder(node5);
        System.out.println("第一个链表");
        singleLinkedListOne1.list();

        SingleLinkedListOne singleLinkedListOne2 = new SingleLinkedListOne();
        singleLinkedListOne2.addOrder(node4);
        singleLinkedListOne2.addOrder(node2);
        singleLinkedListOne2.addOrder(node6);
        System.out.println("第二个链表");
        singleLinkedListOne2.list();

        // 合并两个链表

    }

    public SingleLinkedListOne addOrderSingleList(SingleLinkedListOne singleLinkedListOne1, SingleLinkedListOne singleLinkedListOne2) {
        Node head1 = singleLinkedListOne1.getHead();
        Node head2 = singleLinkedListOne2.getHead();
        Node temp1 = head1;
        Node temp2 = head2;
        SingleLinkedListOne TempSingleList = singleLinkedListOne1;
        while (true) {
            if (temp1.next == null) {
                return singleLinkedListOne1;
            }
            if (temp2.next == null) {
                return singleLinkedListOne2;
            }

//            if (temp1.next.no > temp2.next.no) {
//                temp1.next = temp2.next;
//                temp2.next = temp1.next.next;
//            }




        }

    }
}


class SingleLinkedListOne {

    Node head = new Node(0, "");

    public Node getHead() {
        return head;
    }

    /**
     * 添加到链表
     *
     * @param node
     */
    public void add(Node node) {
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    /**
     * 按顺序插入
     * @param node
     */
    public void addOrder(Node node) {
        Node temp = head;
        boolean flag = false;
        while (true) {
           if (temp.next == null) {
               break;
           }
           if(temp.next.no > node.no) {
               flag = false;
               break;
           }
           if (temp.next.no == node.no) {
               break;
           }
           temp = temp.next;
        }
        if (flag) {
            System.out.println("所插入的已经存在");
        } else {
            node.next = temp.next;
            temp.next = node;
        }
    }



    /**
     * 输出链表的信息
     */
    public void list() {
        if (head.next == null) {
            System.out.println("链表中没有数据");
            return;
        }
        Node temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

}

class Node {
    public int no;
    public String name;
    public Node next;

    public Node(Integer no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ""+
                '}';
    }
}
